LeetCode刷题 | 算法

Author Avatar
yaotao 7月 04, 2018

数据结构与算法

  • LeetCode两题（两数之和，两数相加）
  • 为了复习数据结构和算法刷的题
  • 用比较白话的方式表达个人的理解

一、两数之和

图片

给定一个数组，以及一个数，求数组内是否存在两数和能得到这个数的，有就输出位置
时间复杂度减少需要使用到哈希表

1.暴力穷举法

  • for循环将所有可能循环遍
  • 时间复杂度：O(n2)
  • 空间复杂度：O(1)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
            return new int[] { i, j };
                }
            }
        }
      throw new IllegalArgumentException("No two sum solution");
    }

    /*
    for循环所有可能，每个数都和其他数进行匹配
    效率底，比较傻瓜式
    */

2.两遍哈希表

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
        public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
                }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
                    }
            }
        throw new IllegalArgumentException("No two sum solution");
    }

        /*
        1.使用哈希表（对于iOS开发，哈希表就相当于字典），将数组中的值以键值对的方式放到哈希表中
        2.条件已知 "和" -> target，以及其中一个数（就是数组取的每个值）， 那我们就能得到另外一个数是多少
            即  target - nums[i] = ？
            求得的 ？  可以作为key  数组里面的值变成了Key，每个值对应的下标变成了Value
        问题简单化，使用哈希表键值对的特性，巧妙利用 '数组值' 作为哈希表的 'key''对应下标'作为哈希表的'value'
            判断是否存在,存在的话就说明有对应两数，不存在就没有
        */

3.一遍哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (map.containsKey(complement)) {
    return new int[] { map.get(complement), i };
        }
    map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

/*
在上述两遍哈希表中其实是对哈希表执行了两遍，第一遍是将数组的数据丢进哈希表，第二遍是遍历
第一遍是将数组的数据丢进哈希表的这一步，可以取巧，在下面一次遍历中判断添加，这样不会漏掉数据，且只对哈希表操作一次
*/

二、两数相加

图片

1.单链表

  • 这里必须要复习下单链表的逆序（虽然用处不大）
  • 单链表逆序
  • 本意是使用prev所指向的nil 从头结点开始进行逆序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    1.
    head->next = prev;  //将head的next指针指向prev对应的节点
    prev = head;        //将prev指向head所在的节点，这样head以及prev同时指向头结点
    head = next;        //将head向后移，这个时候head和next指向的都是next所在的节点
    next = head->next;  //最后next 指向head所指向的next（因为前一步head已经和next指向了同一个节点）将next向后移

    2.
    next = head->next;
    head->next = prev;
    prev = head;
    head = next;

    这里的两种循环本体的区别
    第一种在循环到最后当head和next都指向nil的时候，next还需要向后移一步，这个时候肯定是越界的
    第二种方法将 next = head->next; 提到了第一步，先后移，巧妙的避开了第一种的弊端

2.言归正传

给两个单链表，用于保存两个非负整数，逆序存放，求两数之和
(2 -> 6 -> 4) + (1 -> 7 -> 3) = ( 3 -> 3 -> 8)
462 + 371 = 833

  • 这里的逆序已经是提供了便利的条件了

  • 将两个链表顺序执行相加，若大于10，后一位加1

  • 若链表执行到nil 表示执行到了链表尾部节点

  • 当两个链表指针指向的节点都为空时候 结束

  • 题目可以出的更麻烦一点，数字不逆序，这样在计算的时候需要对两个单链表进行一遍的逆序再执行如下操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode nNode = new ListNode(0); // new一个新的 ListNode
    ListNode p =  l1 , q = l2 , arr = nNode; //用p指代l1  q指代l2   arr指代nNode，好看一点

    int carry = 0;//若相加大于10，后一个节点相加需要加上1的，这个carry 用于存放这个1

    while(p != null || q != null){          //只要有一个节点不为null 就要继续执行
        int a = (p != null) ? p.val : 0;    //三目运算判断节点是否为null，为null就取0
        int b = (q != null) ? q.val : 0;    //三目运算判断节点是否为null，为null就取0
        int num = carry + a + b;            //相加得到对应新节点的值
        carry = num / 10;                   //取整，判断相加是否超过10了
        arr.next = new ListNode(num % 10);  //对新链表赋值
        arr = arr.next;                     //arr指向下一个节点，用于下一个循环使用
       
       if(p != null) p = p.next;           //判断链表是否到了尾节点,没有就指向下一个节点
        if(p != null) p = p.next;           //判断链表是否到了尾节点,没有就指向下一个节点
    }
    if(carry > 0){                          //若循环结束carry还大于0，表示最后一个有值的节点相加大于10，新链表需要再增加一个节点存放这个值
        arr.next = new ListNode(carry);     //存放最后一个一个值
    }
    return nNode.next;
}